package com.lzhsite.leetcode.algoritom.practise.string;
/*
	给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。
	示例：
	输入：S = "ADOBECODEBANC", T = "ABC"
	输出："BANC"
	提示：如果 S 中不存这样的子串，则返回空字符串 。如果 S 中存在这样的子串，我们保证它是唯一的答案。
*/
public class LeetCode076最小覆盖子串 {

	public static int getMinCoverSubString(String str1, String str2) {

		char[] str1Arr = str1.toCharArray();
		char[] str2Arr = str2.toCharArray();

		//str1欠str2的总字符数
		int match =0;
		//str1欠str2的每个字符的具体数量
		int map[] = new int[256];
		for (int i = 0; i < str2Arr.length; i++) {
			map[str2Arr[i]]++;
			match++;
		}


		//最小覆盖子串的长度
		int minLen = Integer.MAX_VALUE;
		int left=0,right=0;
		
		while (right < str1.length()) {
			
			//右指针每移动一次map对应的所欠字符数都要减1
			map[str1Arr[right]]--;
			//剩余欠str2的个数如果大于等于0那么欠str2的总字符数就要减1
			if(map[str1Arr[right]] >= 0){
				match--;
			} 
			
			//右指针扩张完毕,左指针开始收缩
			if(match==0){

				//map对应的所欠字符数小于0时才要累加
				//表示剔掉left对应的map值后也不会欠str2
				while (map[str1Arr[left]] < 0) {
					map[str1Arr[left]]++;
					left++;
				}
				//退出while的时map[str1Arr[left]]一定为0，因为右指针在移动的过程中已经让所有欠str2的值为0
				
				//计算好长度后左指针需要移动一步，让此时的长度不符合要求,好寻找新的滑动窗口
				minLen = Math.min(minLen, right-left+1);
				map[str1Arr[left]]++;
				match++;
				left++;

			}
			right++;
		}
		
		return minLen;
	}
	public static void main(String[] args) {
		String S = "ADOBECODEBANC", T = "ABC";
		System.out.println(getMinCoverSubString(S,T));
	}

}
